package binaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
 *@description 二叉树的层平均值
 *@author hkfan
 *@version 1.0
 *@create 2025/6/10 14:46
 */
public class LeetCode_637 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Double> averageOfLevels(TreeNode root) {
        //1. 特殊情况
        if (root==null){
            return new ArrayList<>();
        }
        //2. 定义
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Long sum= 0L,count = 0L;
        //3. 初始化
        queue.add(root);
        queue.add(null);
        //4. 循环
        while (!queue.isEmpty()){
            Boolean flag = false;
            TreeNode node = queue.poll();
            if (node==null){
                continue;
            }
            if (queue.peek()==null && (!queue.isEmpty())){
                sum+=node.val;
                count++;
                res.add(sum*1.0/count);
                sum=0L;count=0L;
                flag=true;
            }
            if (queue.peek()!=null && (!queue.isEmpty())){
                sum+=node.val;
                count++;
            }
            if (node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
            if (flag){
                queue.add(null);
            }
        }
        return res;
    }


}
